#include<iostream>
#include<cstdlib>
#include<map>
using namespace std;

struct ListNode {  
    int val;  
    ListNode *next;  
    ListNode(int x) : val(x), next(NULL) {}  
};  

class Solution
{
public:
    // 辅助函数：打印链表  
    void printList(ListNode* head) {  
        while (head) {  
            std::cout << head->val << " ";  
            head = head->next;  
        }  
        std::cout << std::endl;  
    }  
    
    // 辅助函数：创建链表  
    ListNode* createList(int arr[], int n) {  
        if (n == 0) return nullptr;  
        ListNode* head = new ListNode(arr[0]);  
        ListNode* curr = head;  
        for (int i = 1; i < n; ++i) {  
            curr->next = new ListNode(arr[i]);  
            curr = curr->next;  
        }  
        return head;  
    }  
    
    // 辅助函数：释放链表内存  
    void deleteList(ListNode* head) {  
        while (head) {  
            ListNode* temp = head;  
            head = head->next;  
            delete temp;  
        }  
    }  

    bool check(ListNode* head)
    {
       // 创建一个哑节点作为头节点的前驱  
        ListNode dummy(0);  
        dummy.next = head;
        ListNode* prev = head;
        ListNode* cur = head;
        int prod = 1;
        while(cur)
        {
            prod*= cur->val;
            while(prev != cur && abs(prod) > 10)
            {
                prod /= prev->val;
                prev = prev->next;
            }
            if(prod == 10)
            {
                return true;
            }
            cur = cur->next;
        }
        // 返回哑节点的下一个节点作为新的头节点  
        return false; 
    }
    //利用滑动窗口模型，采用双指针，找到需要删除的范围
    //范围可能出现交叉或者覆盖，暂时用map 保存每个节点指针，方便后期删除
    ListNode* removeSublists(ListNode* head)
    {
        ListNode dummy(0);  
        dummy.next = head;
        ListNode* prev = head;
        ListNode* cur = head;
        map<ListNode*, int> m_p;
        int prod = 1;
        while(cur)
        {
            prod*= cur->val;
            while(prev != cur && abs(prod) > 10)
            {
                prod /= prev->val;
                prev = prev->next;
            }
            if(prod == 10)
            {
                ListNode* tp = prev;
                while(tp != cur)
                {
                   m_p[tp] = tp->val;
                   tp = tp->next;
                }
                m_p[cur] = cur->val;
            }
            cur = cur->next;
        }
        ListNode* p_r = &dummy;//最终需要删除的指针
        ListNode* p_rp = head;//遍历
        while(p_rp)
        {
            if(m_p.count(p_rp) == 0)
            {   
                p_r->next = p_rp;
                p_r = p_r->next;
            }
            p_rp = p_rp->next;
        }
        p_r->next = p_rp;
        map<ListNode*, int>().swap(m_p);
        return dummy.next;
    }

    void fun(int* nums, int numsSize)
    {//测试数组中符合的乘积，输出范围
        //滑动窗口数数组模型
        int ret = 0;
        int prod = 1, i = 0;
        for (int j = 0; j < numsSize; j++) {
            prod *= nums[j];
            while (i <= j && abs(prod) > 10) {
                prod /= nums[i];
                i++;
            }
            //cout << prod << endl;
            if(prod == 10){
                cout <<"范围： " << i << " " << j <<";";
            }
        }
    }

};
  
int main() {  
    int arr[] = {-2,5,-1,-10,1,-1,10,2,2,2,5,5}; 
    Solution sol_list;
    ListNode* head = sol_list.createList(arr, sizeof(arr) / sizeof(arr[0]));
    std::cout << "Original List: ";  
    sol_list.printList(head);
    //sol_list.fun(arr, 14);
    while(sol_list.check(head))
    {
        head = sol_list.removeSublists(head);  
        std::cout << "List after removing product-ten nodes: ";  
        sol_list.printList(head);  
    }   
  
    sol_list.deleteList(head); // 释放链表内存  
    return 0;  
}
